显然是一道回文自动机板题。
设 表示以 号点为左端点的最长回文串 , 表示以 号点为右端点的最长回文串。
可以通过将回文串倒过来建自动机求得 , 可以直接用原回文串建自动机求得。
最后答案为
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 100000 , MAXK = 26;
struct Palindrome_Automaton {
int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
int n , Str[ MAXN + 5 ];
int Len[ MAXN + 5 ] , L[ MAXN + 5 ] , R[ MAXN + 5 ];
void Init( ) {
n = 0 , Size = 0;
memset( Trans , 0 , sizeof( Trans ) );
memset( Link , 0 , sizeof( Link ) );
memset( Len , 0 , sizeof( Len ) );
Root0 = Size ++ , Root1 = Size ++; Last = Root1;
Len[ Root0 ] = 0 , Link[ Root0 ] = Root1;
Len[ Root1 ] = -1 , Link[ Root1 ] = Root1;
}
int Extend( int ch ) {
int u = Last; Str[ ++ n ] = ch;
for( ; Str[ n ] != Str[ n - Len[ u ] - 1 ] ; u = Link[ u ] );
if( !Trans[ u ][ ch ] ) {
int Newnode = ++ Size , v = Link[ u ];
Len[ Newnode ] = Len[ u ] + 2;
for( ; Str[ n ] != Str[ n - Len[ v ] - 1 ] ; v = Link[ v ] );
Link[ Newnode ] = Trans[ v ][ ch ]; Trans[ u ][ ch ] = Newnode;
}
Last = Trans[ u ][ ch ];
return Len[ Last ];
}
void Build1( char *str ) {
Init( );
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
R[ i ] = Extend( str[ i ] - 'a' + 1 );
}
void Build2( char *str ) {
Init( );
int len = strlen( str );
for( int i = len - 1 ; i >= 0 ; i -- )
L[ i ] = Extend( str[ i ] - 'a' + 1 );
}
int Calc( char *str ) {
int Ans = 0 , len = strlen( str );
for( int i = 0 ; i < len - 1 ; i ++ )
Ans = max( Ans , R[ i ] + L[ i + 1 ] );
return Ans;
}
}PAM;
char str[ MAXN + 5 ];
int main() {
scanf("%s", str );
PAM.Build1( str );
PAM.Build2( str );
printf("%d", PAM.Calc( str ) );
return 0;
}